package main.剑指OfferⅡ;

import java.util.*;

public class Day29_Day32 {
    public static void main(String[] args) {
        System.out.println("**************************Day29**************************");
        System.out.println("剑指OfferⅡ085.生成匹配的括号");
        System.out.println("剑指OfferⅡ086.分割回文子字符串");
        System.out.println("剑指OfferⅡ087.复原IP");
        System.out.println("**************************Day30**************************");
        System.out.println("剑指OfferⅡ088.爬楼梯的最少成本");
        System.out.println("剑指OfferⅡ089.房屋偷盗");
        System.out.println("剑指OfferⅡ090.环形房屋偷盗");
        System.out.println("**************************Day31**************************");
        System.out.println("剑指OfferⅡ091.粉刷房子");
        System.out.println("剑指OfferⅡ092.翻转字符");
        System.out.println("剑指OfferⅡ093.最长斐波那契数列");
        System.out.println("**************************Day32**************************");
        System.out.println("剑指OfferⅡ094.最少回文分割");
        System.out.println("剑指OfferⅡ095.最长公共子序列");
        System.out.println("剑指OfferⅡ096.字符串交织");
    }
}

class Offer85{
    List<String> parentheses = new ArrayList<String>();
    StringBuffer temp = new StringBuffer();
    int n;

    public List<String> generateParenthesis(int n) {
        this.n = n;
        process(0, 0);
        return parentheses;
    }

    public void process(int left, int right) {
        if (temp.length() == 2 * n) {
            parentheses.add(temp.toString());
        } else {
            if (left < n) {
                temp.append('(');
                process(left + 1, right);
                temp.deleteCharAt(temp.length() - 1);
            }
            if (right < left) {
                temp.append(')');
                process(left, right + 1);
                temp.deleteCharAt(temp.length() - 1);
            }
        }
    }
}

class Offer86{
    List<List<String>> list;
    public boolean process2(String s){
        char[] str=s.toCharArray();
        int left=0,right=s.length()-1;
        while (left<right){
            if (str[left]!=str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    public void process1(int start,List<String> lastList,String s){
        List<String> curList=new ArrayList<>(lastList);
        if (start>=s.length()){
            list.add(curList);
            return;
        }
        for (int i=1;start+i<=s.length();i++){
            String temp=s.substring(start,start+i);
            if (process2(temp)){
                curList.add(temp);
                process1(start+i,curList,s);
                curList.remove(curList.size()-1);
            }
        }
    }
    public String[][] partition(String s) {
        int start=0;
        list=new ArrayList<>();
        List<String> curList=new ArrayList<>();
        process1(start,curList,s);
        String[][] result=new String[list.size()][];
        for (int i=0;i<list.size();i++){
            result[i]=list.get(i).toArray(new String[list.get(i).size()]);
        }
        return result;
    }
}

class Offer87{
    int n;
    List<String> ans = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        this.n = s.length();
        process(0, s, new ArrayList<String>());
        return ans;
    }

    public void process(int start, String s, ArrayList<String> list){
        int len = list.size();
        if(len > 4) return;
        if(start == n && len == 4){
            // 拼接list中的所有字符串
            String temp = "";
            for(String str : list){
                temp += str+".";
            }
            ans.add(temp.substring(0,temp.length()-1));
            return ;
        }
        for(int i=start;i<n;i++){
            String temp = s.substring(start,i+1);
            int num = Integer.parseInt(temp);
            if(num > 255) return;
            if(num == 0 && temp.length() == 1) {  // 遏制前导零
                list.add(temp);
                process(i+1, s, list);
                list.remove(list.size()-1);
            }else {
                if(num <= 255 && temp.charAt(0) != '0'){
                    list.add(temp);
                    process(i+1, s, list);
                    list.remove(list.size()-1);
                }
            }
        }
    }
}

class Offer88{
    public int minCostClimbingStairs(int[] cost) {
        int length=cost.length;//动态规划表
        int[] dp=new int[length];
        if (length==1) return cost[0];
        for (int i=0;i<length;i++){
            if (i==0||i==1) dp[i]=cost[i];
            else {
                dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];
            }
        }
        return Math.min(dp[length-1],dp[length-2]);
    }
}

class Offer89{
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

class Offer90{
    public int process(int[] nums,int start,int end){
        int result=-1;
        int[] dp=new int[end+1];
        for (int i=start;i<=end;i++){//最后偷第i家
            int max=0;
            if (i==0||i==1){//前两家自身
                dp[i]=nums[i];
                result=Math.max(result,dp[i]);
                continue;
            }
            for (int j=0;j<i-1;j++){//选取最后偷第i家情况的最优选择
                max=Math.max(max,dp[j]);
            }
            dp[i]=max+nums[i];
            result=Math.max(result,dp[i]);
        }
        return result;
    }
    public int rob(int[] nums) {
        if (nums.length==1) return nums[0];
        else if (nums.length==2) return Math.max(nums[1],nums[0]);
        int a=process(nums,1, nums.length-1);
        int b=process(nums,0, nums.length-2);
        return Math.max(a,b);
    }
}

class Offer91{
    public int minCost(int[][] costs) {
        int length=costs.length;
        int[][] dp=new int[length][3];
        for (int i=0;i<length;i++){
            if (i==0){
                dp[i][0]=costs[i][0];
                dp[i][1]=costs[i][1];
                dp[i][2]=costs[i][2];
            }
            else {
                dp[i][0]=costs[i][0]+Math.min(dp[i-1][1],dp[i-1][2]);
                dp[i][1]=costs[i][1]+Math.min(dp[i-1][0],dp[i-1][2]);
                dp[i][2]=costs[i][2]+Math.min(dp[i-1][0],dp[i-1][1]);
            }
        }
        return Math.min(dp[length-1][0],Math.min(dp[length-1][1],dp[length-1][2]));
    }
}

class Offer92{
    public int minFlipsMonoIncr(String s) {
        int length=s.length();
        char[] str=s.toCharArray();
        int[][] dp=new int[length][2];
        for (int i=0;i<length;i++){
            if (i==0){
                dp[i][0]= str[i]=='0' ? 0 : 1;
                dp[i][1]= str[i]=='1' ? 0 : 1;
            }else {
                dp[i][0]=dp[i-1][0]+(str[i]=='0' ? 0 : 1);
                dp[i][1]=Math.min(dp[i-1][0],dp[i-1][1])+(str[i]=='1' ? 0 : 1);
            }
        }
        return Math.min(dp[length-1][0],dp[length-1][1]);
    }
}

class Offer93{
    public int lenLongestFibSubseq(int[] arr) {
        int max=0,length= arr.length;
        int[][] dp=new int[length][length];
        Map<Integer,Integer> map=new HashMap<>();
        for (int i=0;i<length;i++) map.put(arr[i],i);
        for (int i=0;i<length;i++){
            for (int j=i-1;j>=0&&arr[j]*2>arr[i];j--){
                int temp=map.getOrDefault(arr[i]-arr[j],-1);
                if (temp>=0) dp[j][i]=Math.max(dp[temp][j]+1,3);
                max=Math.max(max,dp[j][i]);
            }
        }
        return max;
    }
}

class Offer94{
    public int minCut(String s) {
        int length=s.length();
        boolean[][] flag=new boolean[length][length];
        for (boolean[] cur:flag) Arrays.fill(cur,true);
        for (int i=length-1;i>=0;i--){
            for (int j=i+1;j<length;j++){
                flag[i][j]=s.charAt(i)==s.charAt(j)&&flag[i+1][j-1];
            }
        }
        int[] dp=new int[length];
        Arrays.fill(dp,Integer.MAX_VALUE);
        for (int i=0;i<length;i++){
            if (flag[0][i]) dp[i]=0;
            else {
                for (int j=0;j<i;j++){
                    if (flag[j+1][i]) dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[length-1];
    }
}

class Offer95{
    public int longestCommonSubsequence(String text1, String text2) {
        int length1=text1.length(),length2=text2.length();
        char[] str1=text1.toCharArray(),str2=text2.toCharArray();
        int[][] dp=new int[length1][length2];
        for (int i=0;i<length1;i++){
            for (int j=0;j<length2;j++){
                if (j==0){//0列
                    if (str1[i]==str2[j]||(i-1>=0&&dp[i-1][j]==1)) dp[i][j]=1;
                }else if (i==0){//0行
                    if (dp[i][j-1]==1||str1[i]==str2[j]) dp[i][j]=1;
                }else {
                    if (str1[i]==str2[j]) dp[i][j]=dp[i-1][j-1]+1;
                    else dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[length1-1][length2-1];
    }
}

class Offer96{
    public boolean isInterleave(String s1, String s2, String s3) {
        int length1=s1.length(),length2=s2.length(),length3=s3.length();
        if (length1+length2!=length3) return false;
        char[] str1=s1.toCharArray(),str2=s2.toCharArray(),str3=s3.toCharArray();
        boolean[][] dp=new boolean[length1+1][length2+1];
        dp[0][0]=true;
        for (int i=0;i<=length1;i++){
            for (int j=0;j<=length2;j++){
                int temp=i+j-1;
                if (i>0){
                    dp[i][j]=dp[i][j] || (dp[i-1][j]&&str1[i-1]==str3[temp]);
                }
                if (j>0){
                    dp[i][j]=dp[i][j] || (dp[i][j-1]&&str2[j-1]==str3[temp]);
                }
            }
        }
        return dp[length1][length2];
    }
}